class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> pre(n);
        vector<int> suf(n);


        pre[0] = height[0];
        for (int i = 1; i < n; ++i) {
            pre[i] = max(pre[i - 1], height[i]);
        }

        suf[n - 1] = height[n - 1];
        for (int j = n - 2; j >= 0; --j) {
            suf[j] = max(suf[j + 1], height[j]);
        }

        int capacity = 0;
        for (int k = 0; k < n; ++k) {
            capacity += min(suf[k], pre[k]) - height[k];
        }
        return capacity;
    }
};